package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

import org.junit.Test;

/**
 * Given an array S of n integers, are there elements a, b, c in S such that a +
 * b + c = 0? Find all unique triplets in the array which gives the sum of zero.
 * 
 * Note: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤
 * b ≤ c) The solution set must not contain duplicate triplets. For example,
 * given array S = {-1 0 1 2 -1 -4},
 * 
 * A solution set is: (-1, 0, 1) (-1, -1, 2)
 * 
 * @author yunzhang
 * 
 */
public class ThreeSum {

	/**
	 * Implementation with Set
	 * 
	 * @param num
	 * @return
	 */
	public ArrayList<ArrayList<Integer>> threeSum2(int[] num) {
		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

		if (num.length < 3)
			return result;

		Arrays.sort(num);
		Set<Integer> visited = new HashSet<Integer>();

		for (int i = 0; i < num.length; ++i) {
			if (!visited.contains(num[i])) {
				Set<ArrayList<Integer>> tuples = findTwoSum(num, i);
				if (tuples.size() != 0) {
					for (ArrayList<Integer> tuple : tuples) {
						tuple.add(0, num[i]);
						result.add(tuple);
					}
				}
				visited.add(num[i]);
			}
		}

		return result;
	}

	Set<ArrayList<Integer>> findTwoSum(int[] num, int ignore) {
		Set<Integer> set = new HashSet<Integer>();
		Set<ArrayList<Integer>> twoSums = new HashSet<ArrayList<Integer>>();

		for (int i = ignore + 1; i < num.length; ++i) {
			int missing = 0 - num[ignore] - num[i];
			if (set.contains(missing)) {
				set.remove(missing);
				ArrayList<Integer> twoSum = new ArrayList<Integer>();
				twoSum.add(missing);
				twoSum.add(num[i]);
				if (!twoSums.contains(twoSum))
					twoSums.add(twoSum);
			} else
				set.add(num[i]);
		}

		return twoSums;
	}

	/**
	 * Eliminate duplicate triples without using {@link Set}
	 * 
	 * @param num
	 * @return
	 */
	public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		if (num == null || num.length < 3)
			return result;

		Arrays.sort(num);

		int n = num.length;
		for (int i = 0; i < n; ++i) {
			if (i == 0 || num[i] != num[i - 1]) {
				int j = i + 1;
				int k = n - 1;

				while (j < k) {
					int twoSum = num[j] + num[k];
					if (twoSum < -num[i])
						while (++j < k && num[j] == num[j - 1])
							;
					else if (twoSum > -num[i])
						while (j < --k && num[k] == num[k + 1])
							;
					else {
						ArrayList<Integer> triple = new ArrayList<Integer>(3);
						triple.add(num[i]);
						triple.add(num[j]);
						triple.add(num[k]);
						result.add(triple);
						while (++j < k && num[j] == num[j - 1])
							;
						while (j < --k && num[k] == num[k + 1])
							;
					}
				}
			}
		}

		return result;
	}

	@Test
	public void testSmall() {
		ThreeSum ts = new ThreeSum();
		int[] num = new int[] { -4, -2, -2, -2, 0, 1, 2, 2, 2, 3, 3, 4, 4, 6, 6 };
		ts.threeSum(num);
	}

	@Test
	public void testSmall2() {
		ThreeSum ts = new ThreeSum();
		int[] num = new int[] { -1, 0, 1, 2, -1, -4 };
		ts.threeSum(num);
	}
}